package com.lry.basic.algorithm.graph;

import java.util.*;

public class UndirectedGraphBFS {
    private UndirectedGraph graph;
    private List<Integer> orders = new ArrayList<>();
    private boolean[] visited;

    public UndirectedGraphBFS(UndirectedGraph graph){
        this.graph = graph;
        visited = new boolean[graph.vertexNum()];

        //多个联通分量必须for
        for(int v=0;v<graph.vertexNum();v++){
            if(!visited[v]){
                bfs(v);
            }
        }
    }

    public List<Integer> getOrders(){return orders;}
    private void bfs(int v){
        Queue<Integer> queue = new LinkedList();
        queue.offer(v);
        visited[v] = true;

        while(!queue.isEmpty()){
            int w = queue.poll();
            orders.add(w);
            for(int u:graph.adj(w)){
                if(!visited[u]){
                    visited[u] = true;
                    queue.offer(u);
                }
            }
        }
    }

    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        UndirectedGraphBFS graphBFS = new UndirectedGraphBFS(graph);
        System.out.println(graphBFS.getOrders());
    }
}
